Kőnig's lemma

Lemma

A tree with finite number of branches at each fork and finite number of leaves at the end of each branch (locally finite) is called a finitely branching tree.

A finitely branching tree is infinite (infinitely many edges and/or vertices) iff it has an infinite path (i.e. a ray, a simple path that starts at one vertex and continues through infinitely many vertices)

Notes

• has implications for computability
• results from axiom of dependent choice (?)
• equivalent to statement that every countable family of finite sets admits a choice function
• in Bennett and Gill (1981) paper it is used with recursive operators

References

1. https://en.wikipedia.org/wiki/Kőnig's_lemma
2. https://mathworld.wolfram.com/KoenigsLemma.html
3. https://math.stackexchange.com/questions/3615064/long-detailed-proof-of-kőnigs-lemma-explicit-down-to-axiom-of-choice
4. https://tellerprimer.ucdavis.edu/sites/g/files/dgvnsk14476/files/inline-files/2ch14.pdf